﻿/* 18. *** Write a program that reads an array of integers 
 * and removes from it a minimal number of elements in such way 
 * that the remaining array is sorted in increasing order. 
 * Print the remaining sorted array. 
 * Example: {6, 1, 4, 3, 0, 3, 6, 4, 5} -> {1, 3, 3, 4, 5} */

using System;
using System.Text;
using System.Collections.Generic;

public class SortedArrayWithMaxNumberOfElements
{
    public static int n;
    public static List<double> array = new List<double>();
    public static List<int> elements = new List<int>();
    public static bool found = false;

    public static void Main()
    {
        if (DataInput())
            for (int rest = n; rest > 0; rest--)
            {
                FirstGoodCombination(elements, rest);
                if (found)
                    break;
            }
        else
            Console.WriteLine("\nThe length of array must be natural!\n");
    }

    public static bool DataInput()
    {
        Console.Write("\nThe length of array: ");
        n = int.Parse(Console.ReadLine());
        if (0 < n)
        {
            Console.WriteLine();
            for (int i = 0; i < n; i++)
            {
                Console.Write("Array[{0}] = ", i);
                array.Add(double.Parse(Console.ReadLine()));
                elements.Add(i + 1);
            }

            Console.WriteLine();
            return true;
        }
        else
            return false;
    }

    static void FirstGoodCombination(List<int> elements, int k)
    {
        double last = 0;
        int members = elements.Count;
        int ones = 0;
        StringBuilder combination = new StringBuilder(members);
        for (int i = 0; i < members; i++)
            combination.Append("0");

        do
        {
            if (ones == k)
            {
                found = true;

                for (int j = members - 1; j >= 0; j--)
                {
                    if (combination[j] == '1')
                        last = array[n - elements[j]];

                    for (int g = j - 1; g >= 0; g--)
                        if (combination[g] == '1')
                            if (last <= array[n - elements[g]])
                                last = array[n - elements[g]];
                            else
                            {
                                found = false;
                                break;
                            }

                    break;
                }

                if (found)
                {
                    PrintGoodSubset(combination.ToString());
                    break;
                }
            }

            if (combination[members - 1] == '0')
            {
                combination[members - 1] = '1';
                ones++;
            }
            else if (ones == members)
                break;
            else
            {
                combination[members - 1] = '0';
                for (int i = members - 2; i >= 0; i--)
                {
                    if (combination[i] == '0')
                    {
                        combination[i] = '1';
                        break;
                    }
                    else
                    {
                        combination[i] = '0';
                        ones--;
                    }
                }
            }
        } while (ones <= members);
    }

    public static void PrintGoodSubset(string twine)
    {
        Console.Write("\nOne of all sorted subarrays\nwith maximal number of elements of entered array is\n{0} ", "{");

        for (int j = twine.Length - 1; j >= 0; j--)
            if (twine[j] == '1')
            {
                Console.Write("{0}", array[n - elements[j]]);
                for (int g = j - 1; g >= 0; g--)
                    if (twine[g] == '1')
                        Console.Write(", {0}", array[n - elements[g]]);

                break;
            }

        Console.WriteLine(" {0}\n", "}");
    }
}